package main

import (
	"fmt"
	"reflect"
)

/*
*
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

借助辅助栈 空间换时间
![20180814153425646074359.png](http://cdn.bsummer.cn/20180814153425646074359.png)
*/
type MinStack struct {
	Data    []int
	MinData []int
}

/** initialize your data structure here. */
func Constructor() MinStack {
	return MinStack{Data: []int{}, MinData: []int{}}
}

func (this *MinStack) Push(x int) {

	if len(this.Data) > 0 {
		if this.GetMin() < x {
			this.MinData = append(this.MinData, this.GetMin())
		} else {
			this.MinData = append(this.MinData, x)
		}
	} else {
		this.MinData = append(this.MinData, x)
	}
	this.Data = append(this.Data, x)
}

func (this *MinStack) Pop() {
	this.Data = this.Data[:len(this.Data)-1]
	this.MinData = this.MinData[:len(this.MinData)-1]
}

func (this *MinStack) Top() int {
	return this.Data[len(this.Data)-1]
}

func (this *MinStack) GetMin() int {
	return this.MinData[len(this.MinData)-1]
}

func main() {
	c := Constructor()
	fmt.Println(reflect.TypeOf(c))
	c.Push(-1)
	c.Push(-2)
	fmt.Println(c.GetMin())
}
